package 力扣日常刷题.木23一月.第17天317;

import 力扣日常刷题.TreeNode;

import java.util.HashMap;

/**
 * @author 帅小伙
 * @date 2022/3/17
 * @description
 */
public class Demo89重建二叉树 {

    int[] preorder;
    HashMap<Integer,Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            dic.put(inorder[i], i);
        }

        return build(0,0,preorder.length - 1);
    }

    public TreeNode build(int root,int l,int r) {
        if(l > r) return null;
        TreeNode node = new TreeNode(preorder[root]);
        int i = dic.get(preorder[root]);
        // 左子树的根节点
        node.left = build(root+1,l,i - 1);
        //右子树的根节点  root + i - l +1 ---- root +(i - 1 - l +1) +1
        node.right = build(root + i - l +1,i+1,r);
        return node;
    }

}
